#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
       unordered_map<int,int> indexmap;
       for(int i = 0;i<inOrder.size();i++)
       {
           indexmap[inOrder[i]] = i;
       }
       TreeNode* root = build(preOrder,0,preOrder.size()-1,inOrder,0,inOrder.size()-1,indexmap);
       queue<TreeNode*> que;
       que.push(root);
       vector<int> ret;
       while(!que.empty())
       {
            int size = que.size();
            for(int i = 0;i<size;i++)
            {
                TreeNode* tmp = que.front();
                que.pop();
                if(i == 0)
                {
                    ret.push_back(tmp->val);
                }
                if(tmp->right)
                    que.push(tmp->right);
                if(tmp->left)
                    que.push(tmp->left);
            }
       }
       return ret;
    }
private:
    TreeNode* build(vector<int>& pre,int prebegin,int prend,vector<int>& inor,int inbegin,int inend,unordered_map<int,int>& map)
    {
        if(prebegin>prend||inbegin>inend)
        {
            return nullptr;
        }
        int val = pre[prebegin];
        int index = map[val];
        int leftnum = index-inbegin;
        TreeNode* root = new TreeNode(val);
        root->left = build(pre,prebegin+1,prebegin+leftnum,inor,inbegin,index-1,map);
        root->right = build(pre,prebegin+leftnum+1,prend,inor,index+1,inend,map);
        return root;
    }
};